//
// Created by liushuai on 2021/2/3.
//

#include "addInList.h"
ListNode* addInList(ListNode* head1, ListNode* head2){
    stack<ListNode*> stack1;
    stack<ListNode*> stack2;
    if(!head1)
        return head2;
    if(!head2)
        return head1;
    while (head1){
        stack1.push(head1);
        head1 = head1->next;
    }
    while (head2){
        stack2.push(head2);
        head2 = head2->next;
    }
    int min_stack = stack1.size()<stack2.size()?stack1.size():stack2.size();
    int forward = 0;
    deque<int> res;

    for(int i=0;i<min_stack;i++){
        int value = stack2.top()->val+stack1.top()->val+forward;
        forward = value/10;
        res.push_back(value%10);
        stack1.pop();
        stack2.pop();
    }
    while(!stack1.empty()) {
        int value = stack1.top()->val + forward;
        forward = value / 10;
        stack1.pop();
        res.push_back(value % 10);
    }
    while (!stack2.empty()){
        int value = stack2.top()->val+forward;
        forward = value/10;
        stack2.pop();
        res.push_back(value%10);
    }
    if(forward)
        res.push_back(forward);
    ListNode* head= nullptr;
    ListNode* temp = head;
    while (!res.empty()){
        ListNode* current = new ListNode(res.back());
        if(!temp){
            head = current;
            temp = head;
            res.pop_back();
        }else{
            temp->next = current;
            temp = current;
            res.pop_back();
        }

    }
    return head;

}